﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

class SOl206
{


    public ListNode reverse2(ListNode head)//迭代方法
    {

        ListNode result = new ListNode();
        ListNode next = new ListNode();
        while (head != null) {

            
            next = head.next;
            head.next = result.next;

            result.next = head;
            head = next;
           
        }

        return result.next;
    }
    public ListNode reverse(ListNode head)//递归方法
    {

        if(head == null || head.next == null)
        {
            return head;
        }

        ListNode nextHead = head.next;
        ListNode newhead = reverse(nextHead);//这个函数返回的是新的头结点了,返回的链表的尾节点是nextHead
        nextHead.next = head;//当前节点接到后面
        head.next = null;//尾节点置空
        return newhead;
    }

}
class Program206_2
{
    static void Main206_2(string[] args)
    {

        //先创建一个链表

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        for (int i = 0; i < 10; i++)//这个叫做尾插法
        {
            ListNode newNode = new ListNode(i);


            cur.next = newNode;
            cur = newNode;
        }

        //while (head != null)
        //{
        //    Console.WriteLine(head.val);
        //    head = head.next;
        //}

        SOl206 sol= new SOl206();
        ListNode res= sol.reverse(head.next);
        while (res != null)
        {
            Console.WriteLine(res.val);
            res = res.next;
        }
        Console.ReadKey();  
    }
    


}
